#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
struct tree{
    int data;
    tree* left;
    tree* right;
};
struct brotree{
    int data;
    brotree * left;
    brotree * right;
}
bool pd(tree *root){
    queue <tree*>q;
    q.push(root);
    int bj=0;//标记在此之前是否出现了空结点
    while(!q.empty()){
        tree * f=q.front();
        q.pop();
        if(f=NULL){
            bj=1;
        }
        else{
            if(bj)return 0;
            q.push(f->left);   
            q.push(f->right); 
               }
    return 1;
}
}
int find(tree * root){
    unordered_map<tree *,tree *>umap;
    queue<tree * >q;
    int n=0;
    int size=1;
    tree * last=root;
    q.push(root);
    while(!q.empty()){
        n++;
        for(int i=1;i<=size;i++){
           
            tree * f=q.front();
             if(i==1)last=f;//第一条最长的路径
            q.pop();
            if(f->left!=NULL){
                q.push(f->left);
                umap[f->left]=f;//存储路径
            }
             if(f->right!=NULL){
                q.push(f->right);
                umap[f->right]=f;
            }
        }
        size=q.size();
    }
    tree * path[20000];//假装我知道范围
    for(int i=0;i<n;i++){
        path[n-i]=last;
        last=umap[last];
    }
    for(int i=1;i<=n;i++){
        cout<<path[i]->data;
    }
}
int deepth(brotree * root){
    if(root==nullptr)return 0;
    else {
        int left_depth=deepth(root->left);
        int right=deepth(root->right);
        int cu=left_depth+1;
        return max(cu,right);
    }
}